import java.util.Arrays;
import java.util.Scanner;

public class chap07 {
    //数组详解，实操。。。
    //注：native本地方法：特点底层是有c/c++写的看不见
//给定一个有序整型数组, 实现二分查找
    /*
    1：main1 数组的创建和初始化
    2：main2 数组对象的改变
    3：main3 数组方法的调用
    4：main4 方法创建数组
    5：main5 通过方法对数组元素进行修改
    6：main6 数组元素空间扩容
    7：main7 数组通过不同对象扩容
    8：main8 数组转字符串方法实现
    9：main9 深拷贝与浅拷贝
   10：main10 实例数组元素扩大
   11：main11 实例奇数位于偶数前
   12：main12 实例实现二分查找
   13：main13 实例实现冒泡排序
   14: main14 实例实现寻找俩数之和
   15: main15 实例实现出现次数最少的数
   16: main16 实例实现出现次数最多的数
   17：main17  实例 存在连续三个奇数的数组
   18：main18
     */



    //********************************************
    public static int[] fun15(int [] array){
        int count=0;
        int []ret=new int[3];
        for(int i=0;i<array.length-1;i++){
            if(array[i]%2==1){
                ret[count]=array[i];
                count++;
            }else{
                count=0;
            }
            if(count==3)
            {
                return ret;
            }
        }
        return  ret;
    }
    public boolean threeConsecutiveOdds(int[] arr) {
        //main17标准解法
        // 引入标志位记录连续出现奇数的个数
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (isConsecutiveOdd(arr[i])) {
                // 出现奇数，count ++;
                count ++;
                if (count == 3) {
                    // 出现连着三个奇数，返回true
                    return true;
                }
            }else {
                // 碰到偶数，count重置
                count = 0;
            }
        }
        return false;
    }

    private boolean isConsecutiveOdd(int num) {
        return num % 2 != 0;
    }
    public static void main17(String[] args) {
        //存在连续三个奇数的数组
        int [] array={1,2,34,3,4,5,7,23,12};
        int [] ret=fun15(array);
        for (int i=0;i<ret.length;i++){
            if (ret[i]==0){
                System.out.println("无连续三个");
                break;
            }
            else
            {
                System.out.print(ret[i]+" ");
            }
        }
    }
    //**********************************
    public static int fun14(int [] array){
        int mid=array.length/2;
        int [] ret=new int[array.length];
        for (int i=0;i<array.length;i++){
            for (int j=0;j<array.length;j++){
                if(array[i]==array[j]){
                    ret[i]++;
                }
            }
        }
        for(int i=0;i<ret.length;i++){
            if(ret[i]>mid){
                System.out.println(array[i]);
                break;
            }

        }
        return 0;
    }
    public int majorityElement(int[] nums) {
        //main16标准解法
        //解题思路：数组中出现次数超过一半的数字，一定是排好序之后，中间位置的数字。
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
    public static void main16(String[] args) {
        //给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
        int [] array={2,2,1,1,1,2,2};
        fun14(array);

    }

    //*****************************************
    public static int fun13(int [] array){
        int [] arr=new int[array.length];
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<array.length-i;j++)
            {
                if(array[i]==array[j])
                {
                    arr[i]++;
                }
            }
        }
        for( int i=0;i<arr.length;i++){
            if(arr[i]==1){
                return i;
            }
        }
        return -1;

    }
    public int singleNumber(int[] nums) {
        // main15作业解法，高效简单
        // 用异或运算的性质可以巧妙的解决这个问题，因为数组中只有一个数字出现一次
        // 则其他出现两次的数字用异或运算后都是0，最终整个数组异或运算的结果即为所求。
        int ret = 0;
        for (int i : nums) {
            ret ^= i;
        }
        return ret;
    }

    public static void main15(String[] args) {
        //给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
        int [] array={1,1,2,2,4,5,5,6,6,7,7};
        int n=fun13(array);
        if(n!=-1){
            System.out.println(array[fun13(array)]);
        }else{
            System.out.println("没有出现一次的元素");
        }


    }


    //*******************************************************
    public static int[] fun12(int [] array, int target){
        int [] array1=new int[2];
        boolean flag=false;
        int count=0;

        for (int i=0;i<array.length;i++){
            int k=target-array[i];

            for (int j=0;j<array.length;j++){
                if (array[j]==k){
                    flag=true;
                    array1[0]=j;
                    count++;
                    break;
                }
            }
            if(flag){
                array1[1]=i;
                return array1;
            }

        }
        return array1;


    }
    public static void main14(String[] args) {
        //给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
        int [] array={1,3,5,7,9,2,4,6,8,10};
        int n=20;
        int [] ret=fun12(array,n);

        System.out.println(Arrays.toString(ret));
        System.out.println("下标对应的数字为 "+array[ret[0]]+"+"+array[ret[1]]+"="+n);
    }




    //**************************************
    public static void fun11(int [] array){
        for (int i=0;i<array.length;i++){
            for (int j=0;j<array.length-1-i;j++){
                if (array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }

            }
        }
    }
    public static void bubbleSort(int[] array) {//main13标准解法
        boolean flg = false;
        //1、确定一个趟数
        for (int i = 0; i < array.length-1; i++) {//控制趟数
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flg = true;
                }
            }
            if(flg == false) {
                //没有交换
                break;
            }
        }
    }
    public static void main13(String[] args) {
        //给定一个整型数组, 实现冒泡排序(升序排序)
        int [] array={1,5,8,9,7,2,3,4,6,};
        System.out.println(Arrays.toString(array));
        fun11(array);
        System.out.println(Arrays.toString(array));


    }





    //***************************************************

    public static int fun10(int [] array,int k){
        int left=0;
        int right=array.length-1;

        while(right>=left){
            int mid=(left+right)/2;
            if (array[mid] == k){
                return mid;
            }
            else if (array[mid]>k){
                right=mid-1;
            }
            else if(array[mid]< k){
                left=mid+1;
            }
        }
        return  -1;

    }
    public static void main12(String[] args) {
        //给定一个有序整型数组, 实现二分查找
        Scanner sc=new Scanner(System.in);
        int [] array={1,2,3,4,5,6,7,8,9,10};
        while(sc.hasNextInt()){
            int n=sc.nextInt();//测试边界
            if(fun10(array,n)!=-1){
                System.out.println("查找元素下标为"+fun10(array,n));
            }
            else
            {
                System.out.println("未找到");
            }
        }

    }




    //*****************************************
    public  static  void  fun9(int [] array){

        for (int i=0;i<array.length;i++){
            if (array[i]%2 != 0){
                for (int j=0; j<array.length;j++){
                    if (array[j]%2 == 0){
                        if (i>j){//将奇数换完后，程序继续运行将i下标的偶数与j下标的偶数进行互换
                            int temp=array[i];
                            array[i]=array[j];
                            array[j]=temp;
                        }
                    }
                }
            }
        }


    }

    public static void main(String[] args) {
        //调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序。
        //这个数组排序结果是有序的前提是，数组原来是有序
        int [] array={1,2,3,4,5,6,7,8,9};
        System.out.println(Arrays.toString(array));
        fun9(array);
        System.out.println(Arrays.toString(array));


    }



    //*************************************************
    public static void transform(int [] array){
        for (int i=0;i<array.length;i++){
            array[i]*=2;
        }
    }
    public static void main10(String[] args) {
        //1实现一个方法 transform, 以数组为参数, 循环将数组中的每个元素 乘以 2 , 并设置到对应的数组元素上.
        int [] array={1,2,3};
        transform(array);
        System.out.println(Arrays.toString(array));
    }
    //********************************************
    public static int[] fun8(int[] array,int length){
        //实现my_Array.copy
       // 底层拷贝方法System.arraycopy();
        int [] tmp=new int[length];
        for (int i=0;i<length;i++){
            if(i==array.length){
                break;
            }
            tmp[i]=array[i];
        }
        return tmp;
    }

    public static void main9(String[] args) {
        int [] array={1,2,3,4};
        int [] ret1=Arrays.copyOfRange(array,0,3);//[0,3)
        ret1 = array.clone();//深拷贝，产生一个副本给ret1
        int [] ret=fun8(array,5);
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(ret1));
        System.out.println(Arrays.toString(ret));


    }

    //************************************************
    public static String fun7(int[] array){
        //实现my_toString
        String ret="[";
        if(array == null)
        {
            return "null";
        }
        for(int i=0; i<array.length;i++){
            if(i == array.length-1){
                ret+=array[i];
            }else{
                ret+=array[i]+",";
            }
            if(i==array.length-1){
                ret+="]";
            }
        }
        return ret;
    }
    public static void main8(String[] args) {
        //数组转字符串
        int [] array={1,2,3,4};
        System.out.println(fun7(array));
        int [] array1=null;
        System.out.println(fun7(array1));


    }
    //*****************************************
    public static int[] fun6(int[] array){
        //不是一个对象扩容
        int [] tmpArray=new int[array.length];
        for(int i=0; i < array.length ; i++){
            tmpArray[i]=array[i]*2;
        }
        return tmpArray;
    }
    public static void main7(String[] args) {
        int [] array={1,2,3,4,6,7,8};
        int [] ret=fun6(array);
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(ret));

    }
    //*************************************
    public static int[] fun5(int[] array){
        //数组元素空间扩容
        int [] array2=Arrays.copyOf(array,array.length+5);
        for (int i=0;i<array2.length;i++){
            array2[i]=i;
        }
        return array2;

    }
    public static void main6(String[] args) {
        int [] array={1,2,3,4,5};
        System.out.println(Arrays.toString(array));
        array=fun5(array);
        System.out.println(Arrays.toString(array));

    }
    //*********************************************
    public static int[] fun4(int[] array){
        //数组元素扩充，在同一个对象进行修改
        for(int i=0;i <array.length;i++){
            array[i]=array[i]*2;
        }
        return array;
    }
    public static void main5(String[] args) {
        int [] array={1,2,3,4,5,6,7,8};
        int [] ret=fun4(array);
        System.out.println(Arrays.toString(array));
       // System.out.println(Arrays.toString(ret));

    }
    //***************************************
    public static int[] fun3(){
        int [] temp={1,23,4};
        //函数temp栈被销毁，但是对象是在堆中，地址被返回回去，堆中数据并不被销毁

        return temp;
    }
    public static void main4(String[] args) {
        int [] array=fun3();
        System.out.println(Arrays.toString(array));
    }
    //********************************************
    public static void fun1(int [] array){
        array =new int[]{15,16,17,18};
        //只是改变了形参的指向，并没有改变实参的指向

    }
    public static void fun2(int [] array){
        array[0]=9999;

    }

    public static void main3(String[] args) {
        int [] array1={1,2,3,4};
        fun1(array1);
        System.out.println(Arrays.toString(array1));
        fun2(array1);
        System.out.println(Arrays.toString(array1));


    }
    public static void main2(String[] args) {
        int [] array1={1,2,3,4};//1 2 3 4 不引用就被回收（系统自动回收）
        int [] array2={11,22,33,44};
        array1=array2;
        array1[0]=18888;
        System.out.println(Arrays.toString(array1));
        System.out.println(Arrays.toString(array2));
        System.out.println(array1);
        System.out.println(array2);
        //当俩个引用指向同一个对象时，通过其中任何一个引用，修改这个对象的值，另一个引用去访问时也是会被改变的

    }
    public static void main1(String[] args) {
        //数组是一个对象，是引用类型
        //
        int [] array=null;//指array这个引用不指向任何对象
        //java局部变量必须复制才能复制
        System.out.println(array);
        int [] array1={1,2,3,4};
        array1[0]=99;
        int [] array2=array1;
        array2[0]=100;
        System.out.println(Arrays.toString(array1));//打印结果一样，说明array2并没有创建一个新数组
        System.out.println(Arrays.toString(array2));
        System.out.println(array1);
        System.out.println(array2);
    }
}
